package com.zjj.algorithm.learning.leetcode.sort;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 791. 自定义字符串排序 中档题
 * 给定两个字符串 order 和 s 。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序。
 * <p>
 * 对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，
 * 那么在排列后的字符串中， x 也应该出现在 y 之前。
 * <p>
 * 返回 满足这个性质的 s 的任意一种排列 。
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: order = "cba", s = "abcd"
 * 输出: "cbad"
 * 解释:
 * “a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
 * 因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。
 * 示例 2:
 * <p>
 * 输入: order = "cbafg", s = "abcd"
 * 输出: "cbad"
 *
 * @author zjj_admin
 * @date 2022/11/18 10:07
 */
public class CustomSortString {

    public static void main(String[] args) {
        String order = "cbafg";
        String s = "abcd";
        String res = customSortString(order, s);
        System.out.println("res = " + res);

    }


    /**
     * 不好理解啊
     * @param order
     * @param s
     * @return
     */
    public static String customSortString(String order, String s) {
        //定义一个 map 用于存放所有的字母的优先级
        int[] mp = new int[26];
        //这样就为order中的每一个字符指定了优先级
        for (int i = 0; i < order.length(); i++) {
            int index = order.charAt(i) - 'a';
            mp[index] = i;
        }
        //cbafg 对应的 mp 如下
        //mp = [2, 1, 0, 0, 0, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        //在 mp 数组中 m[0] = 2 ，其中 “2” 表示字符 c，在第一位表示 c 的优先级最高
        System.out.println("mp = " + Arrays.toString(mp));
        List<Character> list = new ArrayList<>();
        for (char c : s.toCharArray()) {
            list.add(c);
        }
        list.sort((a, c) -> {
            int x1 = mp[a - 'a'];
            int x2 = mp[c - 'a'];
            return x1 - x2;
        });
        return list.stream().map(ch -> String.valueOf(ch)).collect(Collectors.joining());

    }

}
